COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0BDR25\M1BDJ25\M2SUB\M3NGB25\M4BEESIX\.
C00024 ENDMK
C⊗;
\\M0BDR25;\M1BDJ25;\M2SUB;\M3NGB25;\M4BEESIX;\.
\F0\CRECURSION


\J	The  term recursion  refers to  several  related concepts  in
computer science and mathematics.\.


Recursion relation

\J	One or more functions of an integer variable is defined by giving
initial values and by giving the value for larger integers in terms of
smaller ones.  No single definition is generally accepted, so we shall
give examples of increasing complexity.\.

	1. The Fibonacci sequence is given by the equations

        \F1f\F20\F1 = 1

        f\F21\F1 = 1

        f\F2n+1\F1 = f\F2n\F1 + f\F2n-1.\F0

\J	2. When differential equations are to be solved numerically,
recursion relations such as\.

     \F1f(x\F20\F1 + nh) = F(f(x\F20\F1 + (n-1)h) , f(x\F20\F1 + (n-2)h) , . . . , f(x\F20\F1 + (n-k)h))\F0


arise where \F1f\F0  is in general a vector of real numbers.

\J	3. When linear differential equations are solved by series, recursion
relations for the coefficients of the powers of the independent variables arise.\.

Recursive functions

\J	The systematic study of recursion began in the 1920's when mathematical
logic began to treat questions of definability, computability and decidability.
An important role is played by primitive recursive functions.

	Primitive recursive functions are integer functions of integers
built up from addition and multiplication of
integers and previously defined primitive recursive functions by the primitive
recursion scheme\.

        \F1f(0 , x\F22\F1 , . . . , x\F2n\F1) = g(x\F22\F1 , . . . , x\F2n\F1)

	f(x\F21\F1 + 1, x\F22\F1 , . . . , x\F2n\F1)\;
 = h(f(x\F21\F1 , . . . , x\F2n\F1),x\F22\F1, . . . , x\F2n\F1n) .\F0

\J	Here \F1g\F0 and \F1h\F0 are primitive recursive functions of \F1n-1\F0
and \F1n+1\F0 arguments respectively.  As an example, we define \F1n!\F0 by

	0! = 1

and

	\F1(n+1)! = (n+1).n!\F0

so that in this case \F1g\F0 is a function of 0 arguments, namely the constant 1,
and \F1h(u,v) = (v+1)u.\F0\.

\J	All the common functions of number theory are primitive recursive.
Moreover, many important functions on other countable domains than the
integers correspond to primitive recursive functions when we choose a specific
enumeration for the domain.\.

\J	Primitive recursive functions are included in general recursive
functions.  The definition of general recursive function is like that given above
for primitive recursive functions except that the relations  are replaced
by an arbitrary finite collection of equations relating the values of \F1f\F0
for different arguments, and the function is considered defined \F3if and only
if\F0 a unique value of \F1f(x\F21\F1 , . . . , x\F2n\F1)\F0 can be deduced from the equations for
each \F1n\F0-tuplet \F1(x\F21\F1 , . . . , x\F2n\F1)\F0.  Naturally, if someone gives you an arbitrary
collection of such relations, you may not be able to determine whether
\F1f(x\F21\F1 , . . . , x\F2n\F1)\F0 is uniquely determined, so you may not know whether you have
a general recursive function or not.  This difficulty is unavoidable.  There is
no  way to give a definition scheme that is always guaranteed to give a function
but which will give all computable functions.
This fact is itself expressed in
the terminology of recursive function theory by the statement
that the set of computable functions is recursively enumerable but not
recursive.  The famous example of a general recursive function that is not
primitive recursive is the Ackermann function defined by the equations\.

	\F1A(0,n,p) = n + p,
	A(1,0,p) = 0,
	A(2,0,p) = 1,
	A(m+1,0,p) = p \F0if \f1p > 1, and
	A(m+1,n+1,p) = A(m,A(m+1,n,p),p).\F0

\J	An important result for computer science is that the general recursive
functions coincide with the functions defined by Turing machines which are
a simple form of computer.  They also coincide with the functions of
integers defined by Algol or Fortran programs assuming that the program can
cope with whatever size integers arise.\.

\J	Both programs and general recursion schemata in general give partial
functions, because the computation may terminate for some values of the arguments
and not for others.\.

\J	The study of computable functions is the domain of recursive function
theory, an active branch of mathematics.  The connection between current research
in recursive function theory and computing practice or even current research
in computer science is rather tenuous.  This situation might change because
of developments in either field.\.


Recursive procedures

\J	In programming, it is frequently convenient to have a procedure use
itself as a subprocedure.  If the procedure does this, it is called recursive.
Recursive procedures are particularly natural in dealing with symbolic
expressions, because the structure of the programs often match the
structure of the data.
As far as programming languages are concerned, recursive procedures are quite
natural; it requires a special statement in the definition of the language
to forbid them.  However, implementing them requires that a special kind
of object code be compiled, and early programming languages like Fortran
don't allow them.  The problem is that variables in the program correspond to
locations in the machine, and when the program is called by itself, it
will use these same locations forgetting their previous contents.
Therefore, recursive programs use an array, called the \F1stack\F0 to store the
contents of registers that must be saved.  This storage can
be done by the calling routine before it enters the subroutine or it can
be done by the subroutine before it uses the registers, the latter being
more common.  After the registers have been saved on the stack, the index
into the stack is increased by the number of registers stored so that
subsequent saving on the stack will use fresh registers.  When the subroutine
exits the contents of the saved registers are restored from the stack to
their previous values  and the stack pointer
is reduced by the amount it was previously increased.
This is done by the caller or by the subroutine
according to whether the caller or subroutine did the original storing.
An alternative technique is to use the stack for all temporary registers.
In this case, it is unnecessary to move data around and it is only necessary
to change the stack pointer when subroutines are entered and left.  However,
this technique uses up the indexing capabilities of some machines which
may be wanted for other purposes.
Recursive programs can be written in any programming language by
explicitly programming the saving and restoring.

	The first language to use recursive subroutines on a regular basis
were the IPL languages of Newell, Shaw and Simon.  Lists were used for the
stack and the saving and restoring was done explicitly by the programmer.
The first language provide an automatic mechanism for recursion
was LISP.
Algol 60 and its successors allow recursion.

	Many computers have special instruction for handling stacks, e.g.
the PUSH and POP instructions of the Digital Equipment PDP-10.  Other
machines, such as the Burroughs 5000 and its successors,
have instructions that use a hardware
stack directly.  These special facilities give a modest increase in the
efficiency of recursive programming.\.


Recursive conditional expressions

\J	The recursive use of conditional expressions provides an economical
and elegant
way of specifying the functions that are computable in terms of a collection
of base functions.  This technique is the basis of the LISP programming
language and also of the theoretical system of D. Scott for studying
the properties of computer programs.\.

	A conditional expression has the form, in Algol notation, of


        \F3if \F1p \F3then \F1a \F3else \F1b\F0.

\JIt is evaluated by first evaluating the propositional expression \F1p\F0.
If \F1p\F0 is \F3true\F0, the value of the conditional expression is that of
\F1a\F0, and if the value of \F1p\F0 is \F3false\F0, the value of the conditional
expression is that of \F1b\F0.  It is important to note that only
one of \F1a\F0 or \F1b\F0 is actually evaluated.

	A simple example of the use of conditional expressions is to define
the absolute value of a number by\.

	\F1|x| = \F3if\F1 x < 0 \F3then\F1 -x \F3else\F1 x.\F0

\J	Conditional expressions are used to define functions recursively
by writing the definition in the form\.

       	\F1f(x , . . . , z) ← \F4E\F1{x , . . . , z, f , g , . . . , h}\F0,

\Jwhere \F4E\F0 is an expression involving the variables,\F1x , . . . , z\F0,
the function \F1f\F0 being defined, and known or previously defined
functions \F1g , . . . , h\F0.

	An example of such a definition is\.

(\f1a)	\F1n! ← \F3if\F1 n = 0 \F3then\F1 1 \F3else\F1 n.(n-1)!\F0.

\J	The general method for evaluating recursive conditional expressions
is illustrated by using the above definition to evaluate 3!.  Namely,
we have\.

        3! = \F3if\F1 3=0 \F3then \F11 \F3else \F13.(3-1)!
       	   = 3.2! =3.(\F3if\F1 2=0 \F3then \F11 \F3else \F12.(2-1)!)
	   = 3.2.(\F3if \F11=0 \F3then \F11 \F3else \F11.(1-1)!)
	   = 3.2.1.(\F3if \F10=0 \F3then \F11 \F3else \F10.(0-1)!)
	   = 3.2.1.1 = 6.\F0

\JNote that the rule for evaluating conditional expressions ensures that
the computer never attempts to evaluate (-1)!.
This is necessary since its evaluation
wouldn't terminate.

	As a second example, the Ackermann function mentioned above is
written as a recursive conditional expression as follows:\.

	\F1A(m,n,p) ←
		\F3if \F1m = 0 \F3then \F1n + p
		\F3else if \F1n = 0 \F3then \f1(if \F1m = 1 \F3then \f10\;
 else if \F1m = 2 \F3then \f11 else \F1p)
		\F3else \F1A(m - 1,A(m,n - 1,p),p).\F0

\J	Several remarks are worth making:

	First, in a programming language that uses recursive conditional
expressions, 3! would not be evaluated by the above symbolic manipulation.
Either \F1(a)\F0 would be compiled into a recursive subroutine (i.e. a subroutine
of the type explained above that calls itself and uses a stack to save
intermediate results and return addresses) or a recursive interpreter would
interpret a list structure version of \F1(a)\F0.

	Second, \F1(a)\F0 can easily be replaced by another expression for the
factorial that can be compiled into a non-recursive program.  Namely, we
write\.

(\f1b)	\F1n! ← fact(n, 0, 1)\F0

where

	\F1fact(n, m, p) ← \F3if\F1 m = n \F3then \F1p \F3else \F1fact(n, m+1,(m+1)p).

\J(b) \F0can be translated into a non-recursive program, because the only
occurrence of \F1fact\F0 on the right hand side of the definition appears at the
outer level, i.e. \F1fact(n, m+1,(m+1)p)\F0 gives the value of \F1fact(n, m, p) \F0in
contrast to the the situation in \F1(a) \F0where \F1(n-1)! \F0must be multiplied by
\F1n \F0to give \F1n!.  \F0This allows the object program to contain an ordinary
jump to itself rather than a subroutine call.  When this is possible,
the function definition is called iterative.  Thus \F1fact\F0 is iterative
while the definition \F1(a) \F0is not.  Recursive definitions cannot in general be
replaced by iterative definitions except by encoding the stack as a
variable in the program, and if this has to be done, there is no
advantage in the replacement.

	Third, there may be several occurrences of the function being
defined on the right hand side of the recursive definition, and whether
the evaluation terminates may depend on which occurrence is evaluated
first.  The following example due to Morris shows this:\.

	\F1f(x,y) ← \F3if \F1x=0 \F3then \F10 \F3else \F1f(x-1 , f(y-2, x)).\F0

\JThe reader should evaluate \F1f(2,1)\F0 to convince himself.

	It is also possible to use recursive conditional expressions
to define functions that take functions as arguments or give functions
as results.  However, there remain unsolved problems in getting
compiling algorithms that give efficient object code and give the "right"
answers in all cases.

	The term \F1recursive\F0 is also sometimes applied to
the the Backus-Naur form used to define classes of strings of
symbols.


References

	There is no very good reference for the use of recursion in programming.
McCarthy, John, et.al.,
\F1LISP 1.5 Programmer's Manual\F0 (Cambridge:  MIT Press, 1962) has
some discussion of its implementation
in LISP and Randell, Brian and Russell, L. J., \F1Algol 60 Implementation: Translation and Use of Algol 60
Programs by Computers\F0 (New York:  Academic Press, 1964)
discusses the implementation of recursion
in Algol.  Peter, Rozsa \F1Recursive Functions\F0 (New York:  Academic Press, 1967)
has  a  thorough   treatment  of  subclasses  of   general  recursive
functions.  The standard reference on recursive
function   theory   is   Kleene,   Stephen   C.,   \F1Introduction   to
Metamathematics\F0 (Princeton: D. Van Nostrand Company, Inc.,  1952),
but Kleene, Stephen C., \F1Mathematical Logic\F0 (New York:  John Wiley & Sons, Inc., 1967)
has a more elementary treatment.\.

\J	Two aspects of recursion are current research topics in computer science.
First, the notion of recursive program is being extended in various ways and
ways of implementing these extensions by compilers and interpreters are studied.
Second, the formal properties of recursive programs are studied as part of
mathematical theory of computation which has as its major object the ability
to prove assertions about programs and check these assertions on a computer.
For the first we refer to Bobrow, Daniel and Raphael, Bertram, \F1New Programming Languages
for AI Research\F0 (Palo Alto:  Xerox Research Center, 1973)
and for the second we refer to
Manna, Zohar, \F1Introduction to Mathematical Theory of Computation\F0 
(New York:  McGraw Hill & Company, Inc., 1974) (in press).\.